/*
Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6
Sample Output
Case 1:
- + 1 2 * 3 - 4 5
6
Case 2:
- + 1 * 2 - 3 4 * 5 6
-31
 */
package com.yuan.algorithms.practice201511;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author YouYuan <br>
 *         E-mail:1265161633@qq.com <br>
 *         创建时间：2015年11月7日 上午11:32:40 <br>
 *         说明:将中缀表达式转换为前缀表达式： 遵循以下步骤： (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2； (2) 从右至左扫描中缀表达式； (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1)
 *         如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较； (5) 遇到括号时： (5-1)
 *         如果是右括号“)”，则直接压入S1； (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃； (6) 重复步骤(2)至(5)，直到表达式的最左边； (7) 将S1中剩余的运算符依次弹出并压入S2； (8)
 *         依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
 */
public class 中缀表达式转换为前缀表达式并求值 {

	static Scanner in = new Scanner(System.in);

	public static void main(String[] args) {
		int i = 0;
		while (in.hasNext()) {
			++i;
			String str = in.next();
			System.out.println("Case " + i + ":");
			Stack<String> rpn = r(str);
			long result = rs(rpn);
			System.out.println(result);
		}
	}

	/**
	 * 计算波兰式的值
	 * @param rpn
	 * @return
	 */
	private static long rs(Stack<String> rpn) {
//		Stack<String> s1 = new Stack<String>();
		Stack<String> s2 = new Stack<String>();
		while (!rpn.isEmpty()) {
			String t = rpn.pop();
			if (isNum(t.charAt(0))) {
				s2.add(t);
			} else {
				long a = Long.parseLong(s2.pop());
				long b = Long.parseLong(s2.pop());
				long rs = 0;
				switch(t) {
				case "*":
					rs = a*b;
					s2.add(""+rs);
					break;
				case "+":
					rs = a+b;
					s2.add(""+rs);
					break;
				case "-":
					rs = a-b;
					s2.add(""+rs);
					break;
				case "/":
					rs = a/b;
					s2.add(""+rs);
					break;
				}
			}
		}
		return Long.parseLong(s2.pop());

	}

	/**
	 * 计算前缀表达式
	 * 
	 * @param str
	 * @return
	 */
	private static Stack<String> r(String str) {
		Stack<String> s1 = new Stack<String>();
		Stack<String> s2 = new Stack<String>();
		for (int i = str.length() - 1; i >= 0; i--) {
			char t = str.charAt(i);
			if (isNum(t)) {
				String key = ""+t;
				int j = 1;
				while(i-j >= 0 && isNum(str.charAt(i - j))) {
					key = str.charAt(i - j) + key;
					j++;
				}
				i = i - j + 1;
				s2.add(key);
			} else {
				if (s1.isEmpty() || s1.peek().equals(")")) {
					//如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
					s1.add(""+t);
				} else if (t == ')') {
					s1.add(""+t);
				} else if (t == '(') {
					//如果是左括号“(”，依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
					while(!s1.peek().equals(")")) {
						s2.add(s1.pop());
					}
					s1.pop();
				}else {
					while(!s1.isEmpty()) {
						String temp = s1.peek();
						if (getPriority(""+t) >= getPriority(temp)) {
							//若优先级比栈顶运算符的较高或相等，将运算符压入S1
							s1.add(""+t);
							break;
						} else {
							s2.add(s1.pop());
							//将S1栈顶的运算符弹出并压入到S2中，再次转到循环与S1中新的栈顶运算符相比较
							if (s1.isEmpty()) {
								s1.add(""+t);
								break;
							}
						}
					}
					
				}
			}
		}
		while(!s1.isEmpty()) {
			s2.add(s1.pop());
		}
		Stack<String> ret = new Stack<String>();
		boolean k = false;
		while(!s2.isEmpty()) {
			String g = s2.pop();
			ret.add(g);
			if (k) {
				System.out.print(" "+g);
			} else {
				System.out.print(g);
				k = true;
			}
		}
		System.out.println();
		return ret;
	}
	
	private static boolean isNum(char t) {
		return t >= '0' && t <= '9';
	}

	/**
	 * 返回运算符的优先级
	 * @param temp
	 * @return
	 */
	private static int getPriority(String temp) {
		int priority = 2;
		switch (temp) {
		case "+":
		case "-":
			priority = 2;
			break;
		case "*":
		case "/":
			priority = 3;
			break;
		}
		return priority;
	}
}
